open Graph

module Clique (G: Sig.G)
= struct
	
	let (|>) x y = y x
	
	module N = Oper.Neighbourhood(G)
	open N.Vertex_Set
	
	open Timer.Timer
	
	module ClassicBronKerbosch 
	= struct
		(* choose new vertex from candidates*)
		(* we can write another implementation of this functions and test different approaches *)
		let default_choose_v vs =
			choose vs
			(* also we can use (max_elt vs) or (min_elt vs) *)
			(* we'll use it directly in parametrization of basic_algorithm *)
			
		(* basic algorithm, parameterized by a choose_v function for some experiments *)
		(* return (maximal complete subgraph of g * number of cliques) *)
		let basic_algorithm g choose_v =
			(* test whether nots contain vertex, connected with all vertices from cand *)
			let test_nots nots cand =
				nots
				|> elements
				|> List.for_all (fun v -> compare (inter (N.set_from_vertex g v) cand) cand <> 0)
				|> not
			in
			(* delete vertices, not connected with v *)
			let delete_not_connected v vs =
				(* result is intersection of vs and set of vertices, connected with v *)
				inter (N.set_from_vertex g v) vs
			in
			(* return a pair of current compsub and maxclique*)
			(* we use maxcliquesize variable to decrease the number of size calculating function applications *)
			let rec extend cand nots (compsub, cliquesnum, (maxclique, maxcliquesize)) =
				(* while candidates is nonempty and nots doesn't contain a vertex,   *)
				(* connected with all vertices from candidates                       *)
				if is_empty cand || test_nots nots cand
				then compsub, cliquesnum, (maxclique, maxcliquesize)
				else
					let v = choose_v cand in
					let compsub = add v compsub in
					match delete_not_connected v cand , delete_not_connected v nots
					with
					| c , n when is_empty c && is_empty n ->
					(* if cand and nots without vertices, not connected with chosen v, *)
					(* are empty then compsub is clique                                *)
							extend (remove v cand) (add v nots)
								( remove v compsub ,
									cliquesnum + 1 ,
									(* so, choose the biggest and pass it to the next iteration *)
									let newmaxcliquesize = compsub |> elements |> List.length in
									if newmaxcliquesize >= maxcliquesize
									then (compsub, newmaxcliquesize) 
									else (maxclique, maxcliquesize))
					| c ,	n ->
					(* else calculate new compsub and maxclique *)
							let compsub, cliquesnum, (maxclique, maxcliquesize) = 
								extend c n (compsub, cliquesnum, (maxclique, maxcliquesize)) in
							(* and inerate while loop *)
							extend (remove v cand) (add v nots) 
								(remove v compsub, cliquesnum, (maxclique, maxcliquesize))
			in
			let _, n, (max, _) = extend (G.fold_vertex (fun v vs -> add v vs) g empty) empty (empty, 0, (empty, 0))
			in elements max, n
		
		let maxclique_default g = basic_algorithm g default_choose_v
		let maxclique_heuristic g = basic_algorithm g max_elt 
		
	end 
	
	module Johnston 
	= struct
		(* calculate_s functions calculate set, which we use for combination set increasing *)
		
		let basic_calculate_s possible _ _ = possible
		
		(* in practice this function shows the best time result *)
		let simplified_bk_calculate_s possible intersection g =
			diff possible (N.set_from_vertex g (min_elt intersection))
		
		(* unfortunately whis implementation of generalized_bk_calculate_s is rather *)
		(* slow (or slower than expected), perhaps library functions are slow*)
		(* TODO: write and another implementation of generalized_bk_calculate_s *)
		let generalized_bk_calculate_s threshold choose_j possible intersection g  =
			let rec loop t sizeofs s =
				if is_empty t || (sizeofs <= threshold && sizeofs <> 0) then s
				else
					let j = choose_j t in
					let new_s = diff possible (N.set_from_vertex g j) in
					let new_sizeofs = new_s |> elements |> List.length in
					if new_sizeofs < sizeofs || sizeofs = 0
					then loop (remove j t) new_sizeofs new_s
					else loop (remove j t) sizeofs s
			in
			loop intersection 0 empty 
		
		(* choose new vertex from s set *)
		(* we can write another implementation of this functions and test different approaches *)
		let default_choose_i vs =
			choose vs 
			(* also we can use (max_elt vs) or (min_elt vs) *)
			(* we'll use it directly in parametrization of basic_algorithm *)
			
		(* basic Johnston algorithm, parameterized by calculate_s and choose_i functions *)
		let basic_algorithm g calculate_s choose_i =
			(* we use maxcliquesize variable to decrease the number of size calculating function applications *)
			let rec expand combination intersection possible (cliquesnum, (maxclique, maxcliquesize)) =
				if is_empty intersection
				then 
					(* we've found clique, so, increase counter and choose maximal *)
					(cliquesnum + 1, 
					let newmaxcliquesize = combination |> elements |> List.length in
					if newmaxcliquesize >= maxcliquesize
					then (combination, newmaxcliquesize) 
					else (maxclique, maxcliquesize))
				else 
					let s = calculate_s possible intersection g in
					let rec loop s possible (cliquesnum, (maxclique, maxcliquesize)) =
						if is_empty s then (cliquesnum, (maxclique, maxcliquesize))
						else
							let i = choose_i s in
							let s = remove i s in
							let possible = remove i possible in
							let cliquesnum, (maxclique, maxcliquesize) = 
								let gi = N.set_from_vertex g i in
								expand 
									(add i combination)
									(inter gi intersection)
									(inter gi possible)
									(cliquesnum, (maxclique, maxcliquesize))
							in
							(* iterate loop *)
							loop s possible (cliquesnum, (maxclique, maxcliquesize))
					in
					(* start loop *)
					loop s possible (cliquesnum, (maxclique, maxcliquesize))
				in
				let graphVertices = G.fold_vertex (fun v vs -> add v vs) g empty in
				let (cliquesnum, (maxclique, _)) = 
					if is_empty graphVertices  
					then (0, (empty, 0))
					else expand empty graphVertices graphVertices (0, (empty, 0))
				in
				(maxclique, cliquesnum)
		
		let maxclique_basic_method g = 
			basic_algorithm g basic_calculate_s min_elt
			
		let maxclique_simplified_bk_method g = 
			basic_algorithm g simplified_bk_calculate_s max_elt
		
	end 
	
end
